package q961_repeatedNTimes;

import java.util.Random;

public class Solution_2 {
    /*
    可以每次随机选择两个不同的下标，判断它们对应的元素是否相等即可。如果相等，那么返回任意一个作为答案。
    这种方法将时间复杂度的期望降到了最低 o(1) 期望 4 次结束循环。
     */
    public int repeatedNTimes(int[] nums) {
        int n = nums.length;
        Random random = new Random();

        while (true) {
            int x = random.nextInt(n), y = random.nextInt(n);
            if (x != y && nums[x] == nums[y]) {
                return nums[x];
            }
        }

    }
}
